//
// Created by Administrator on 2021/4/9.
//
/*给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root =[6,2,8,0,4,7,9,null,null,3,5]


示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/


#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
};


class Solution {
public:

    // 利用二叉搜索树的性质，得到从根节点到目标节点的路径
    vector<TreeNode *> getPath(TreeNode *root, TreeNode *target) {
        vector<TreeNode *> path;
        TreeNode *node = root;
        while (node != target) {
            path.push_back(node);
            if (target->val < node->val) {
                node = node->left;
            } else {
                node = node->right;
            }
        }
        path.push_back(node);
        return path;
    }

    // 根据p q的路径，找到它们最近的祖先
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        vector<TreeNode *> path_p = getPath(root, p);
        vector<TreeNode *> path_q = getPath(root, q);
        TreeNode *ancestor;
        for (int i = 0; i < path_p.size() && i < path_q.size(); ++i) {
            if (path_p[i] == path_q[i]) {
                ancestor = path_p[i];
            } else {
                break;
            }
        }
        return ancestor;
    }
};

class Solution2 {  // 一次遍历
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        TreeNode *ancestor = root;
        while (true) {
            // 如果p q 都比root的值大，应该到root的右子树找
            // 如果 p q都比root的值小，应该到root的左子树找
            // 否则，root就是分叉点，即找到了p q 的最近公共祖先
            if (p->val < ancestor->val && q->val < ancestor->val) {
                ancestor = ancestor->left;
            } else if (p->val > ancestor->val && q->val > ancestor->val) {
                ancestor = ancestor->right;
            } else {
                break;  //找到分叉点
            }
        }
        return ancestor;
    }
};

int main() {
    /** 二叉搜索树： 左子节点的值比根节点小，右子节点的值比根节点大
     * */
    auto t9 = TreeNode(5);
    auto t8 = TreeNode(3);
    auto t7 = TreeNode(9);
    auto t6 = TreeNode(7);
    auto t5 = TreeNode(4, &t8, &t9);
    auto t4 = TreeNode(0);
    auto t3 = TreeNode(8, &t6, &t7);
    auto t2 = TreeNode(2, &t4, &t5);
    auto t1 = TreeNode(6, &t2, &t3);
    Solution sol{};
    auto ans = sol.lowestCommonAncestor(&t1, &t7, &t5);
    cout << ans->val;
    return 0;
}